Synchronization is a function that provides or maintains consistency between data sets. For example, a desktop computer may have desktop data sets regarding personal information management (“PIM”). A user of that desktop computer may desire to use that PIM data when she is away from her desktop computer. Therefore, she may desire access to the PIM data while using a laptop computer or a personal digital assistant (“PDA”) such as a phone or other device like a miniature device. In order to accommodate that desire, her laptop computer and PDA may each carry PIM data sets that correspond to the PIM data sets on the desktop computer. The role of the synchronization function is to give the user a common view of her data on each device. This role is generally accomplished by synchronization events when two or more of the devices synchronize.
A common technique for synchronizing devices is by using snapshots of data at a point in time and comparing current data to the snapshot to determine what has changed. For illustration purposes, refer to FIG. 1 where there is shown a model for two devices, a desktop computer 100 and a portable computer 110. Desktop computer has PIM database 101, which keeps current information for PIM data sets that are edited or added on the desktop computer 100. Desktop computer 100 also has snapshot database 102 that is a temporal snapshot of the state of the data (e.g., a snapshot of the data sets taken at some point in time but typically the time of a prior synchronization—perhaps, the most recent synchronization). Similarly, portable computer 110 has portable database 111 for current data (and, like any syncing peer such as portable 110 or PDA 120, may also have a snapshot database). Having these structures in place, we may attempt to synchronize desktop 100 and portable 110. Typical synchronization occurs by comparing both portable database 111 and desktop database 101 with snapshot database 102. During the compare operation, we can then assemble a list of data items that are new or changed in the active databases 101 and 111 as compared to database 102. Finally, to finish out the synchronization, the list of new and changed data may be used to update all three databases 101, 102 and 111.
A problem occurs in the described synchronization process when corresponding data is changed on both the desktop and the portable. For example, suppose that sometime prior to synchronization, Jane Doe's phone number was changed to 877-555-5555 on the Desktop and 800-555-5555 on the portable. During the compare operation (or at another time) the synchronizing system will notice this discrepancy and identify a conflict. In the current commercial art, there is generally no elegant way to resolve this conflict with certainty. Some solutions present an interface to the user and ask her to choose between the two options. Unfortunately, even the user may not remember which piece of data is correct. Other commercial solutions simply create duplicate entries in each database (one with each of the possible data items).
The problem is exacerbated if there are more than two devices carrying the corresponding data sets. For example, referring to FIG. 1, assume that after synchronizing with portable 110, desktop 100 attempts to synchronize with PDA 120. During synchronization, we may discover that PDA 120 carries Jane Doe's phone number as 888-555-555. Unfortunately, in the prior art, we once again have no elegant solution for determining the correct result with certainty. Furthermore, even if we could determine the correct result at this time (e.g. by the user, who remembers), we may be unable to stop the system from having the same problem again the next time portable 110 is synchronized.
Finally, the problem may be generalized for peer-to-peer systems with 3 or more peers. That generalization is that, if peers may synchronize with each other 2 at a time, and a conflict arises there is no way to know if one of the peers carries a more up-to-date data. It is noteworthy, that a time stamp can not resolve the conflict with certainty. This is because as a matter of practical human usage, if two corresponding data items have been changed over the past days or months, that doesn't necessarily mean that the second change is correct. This is especially true if the second change occurred as the result of synchronization with another peer (such “another peer” may have received its data change long ago). Therefore, in the peer-to-peer situation, we would be unable to determine if a detected conflict is, on the one hand, a true conflict, or on the other hand, an apparent conflict that could be correctly resolved (e.g. per user intent) if we understood the history of the data.
Some of the related prior art techniques for synchronization may be found in the following U.S. Pat. No. 5,710,922 “Method for synchronizing and archiving information between computer systems,” which is incorporated herein by reference. In addition, the following pending patent applications offer similarly interesting information and are hereby incorporated by reference: “A Method of Synchronizing Between Three or More Devices” by Toby Paterson and Jerome Lebel, having application Ser. No. 10/853,306 and filed May 24, 2004; “A Method of Synchronizing” by Toby Patterson and Jerome Lebel, having application Ser. No. 10/852,926 and filed May 24, 2004; and “Apparatus And Method For Peer-To-Peer N-Way Synchronization In A Decentralized Environment,” having application Ser. No. 11/157,647 and filed Jun. 21, 2005.
In view of the discussion herein as well as the other problems existing in the prior art, certain embodiments of the invention propose a synchronization system that employs datum history information in a process to provide synchronization services either as an API layer in an operating system or as directly employed by software and systems requiring synchronization.